public class Solution {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        bucketSort(nums, n);
        for(int i = 0; i < n; ++i)
            if(nums[i] != (i + 1))
                return i + 1;
        return n + 1;
    }

    private static void bucketSort(int[] nums, int n) {
        for(int i = 0; i < n; i++) {
            while(nums[i] != i + 1) {

                if(nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1])
                    break;

                int t = nums[i];
                nums[i] = nums[t - 1];
                nums[t - 1] = t;
            }
        }
    }
}